/*
	解法：暴力枚举 或 移动匹配 或 KMP
	为什么：暴力枚举
			枚举 len 从 1 到 n / 2，尝试是否可以将 s 拆成多个长度为 len 的子串；
			如果 n % len != 0，说明不能被整除，直接跳过；
			否则，把这个子串重复 n / len 次，拼接后是否等于原串；
			有一个匹配，就返回 true，否则返回 false。
	时间复杂度：O(n^2)，空间复杂度：O(n)  暴力枚举
 */

#include <iostream>
#include <string>

using namespace std;

class Solution
{
public:
	bool repeatedSubstringPattern(string s)
	{
		int n = static_cast<int>(s.length());
		
		//子串至少需要重复一次，所以子串长度 ≤ n/2
		for (int len = 1; len <= n / 2; len++)
		{
			//子串不能完整多次重复，直接跳过
			if (n % len != 0)
			{
				continue;
			}
			
			string substring = s.substr(0, len);
			string repeated;
			
			for (int i = 0; i < n / len; i++)
			{
				repeated += substring;
			}
			
			if (repeated == s)
			{
				return true;
			}
		}
		
		return false;
	}
};

int main()
{
	Solution solution;
	string s;
	
	cout << "请输入字符串：" << endl;
	cin >> s;
	
	bool result = solution.repeatedSubstringPattern(s);
	
	if (result)
	{
		cout << "true" << endl;
	}
	else
	{
		cout << "false" << endl;
	}
	
	return 0;
}


